Most Internet Protocol (IP) backbone networks are designed on top of a Dense Wavelength Division Multiplexing (DWDM) infrastructure. An IP network is a set of logical links that are statically mapped on the physical links of the fiber network. In a DWDM network, each logical link is assigned one wavelength if wavelength continuity is required, or a sequence of wavelengths if wavelength conversion equipment is present. Further, Internet Service Providers (ISPs) are systematically forced to use the shortest distance path between two Points of Presence (PoPs) in order to meet their promised Service Level Agreements (SLAs). In this environment, several logical links (each using a different wavelength) may traverse the same fiber (or the same conduit), making the IP network vulnerable to a physical link failure, such as a fiber cut, that can bring down a significant fraction of the IP routes.
In the past, a Synchronus Optical network (SONET) was used to offer protection and fast restoration of service. However, due to the cost of optical equipment, most ISPs do not use SONET protection anymore. Instead, they rely on the IP layer to restore the connectivity in case of failure. When equipment fails in the topical network, IP routers detect the failure and update their routing tables with alternate logical links. This approach only succeeds if the remaining set of logical links still forms a connected topology.
Mapping logical links to the physical topology to assure connectivity during failures has already been studied. Prior approaches include an Integer Linear Problem (ILP) formulation that solves the problem for moderate size networks by applying a Branch & Cut algorithm. However, this approach assumes there is only a single logical link between network node pairs and does not take into account any delay constraints.
Topology mapping with wavelength constraints has also been studied. Without wavelength converters, the problem is known as the wavelengths assignment problem (WAP). This problem is similar to the path-coloring problem in standard graphs, which is equivalent to the general vertex-coloring problem. Numerous heuristics have been proposed for different types of topologies. However, these approaches do not balance the tradeoff between running time and quality of the solution.
Accordingly, there remains a need for a system and method for identifying optimal mapping of logical links to the physical topology of a network that incorporates practical considerations, such as delay constraints, wavelength availability and multiple logical links between network node pairs.